perm filename PROB1[1,JMC] blob
sn#005213 filedate 1969-12-30 generic text, type T, neo UTF8
00100 Research Problems in Mathematical theory of computation
00200
00300 1. A blob is a flow chart with multiple entries and exits.
00400 the basic operations on blobs are
00500 a. Deleting an entry from a blob.
00600 b. Connecting an exit to an entry.
00700 c. Putting two blobs side by side.
00800 Any flow chart can be built up from the elementary compute
00900 and test blocks by these operations, or even from an
01000 arbitrary decomposition into sub-charts.
01100 A blob is characterized by the predicates giving
01200 for each entry-exit pair the condition on the state vector
01300 at that entry that corresponds to exit at the given exit,
01400 and by the function for each entry that gives the state
01500 at exit from the blob. Corresponding to each of the
01600 operations on blobs is a way of getting the predicates
01700 and functions of the new blob from those of the old blob.
01800 If we join a pair of exits with a pair of entries the
01900 form of functions and predicates apparently depends
02000 on the order of joining. Problem: to prove by theory of
02100 computation that the functions are equivalent as they
02200 obviously are from the flow chart interpretation.